﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms
{
    class Sort
    {
        public static List<T> ShellSorter<T>(List<T> list, int increament) where T : IComparable
        {
            int n = list.Count;
            //int[] incs = { 1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768, 463792, 1391376, 3402672, 8382192, 21479367, 49095696, 114556624, 343669872, 52913488, 2085837936 };

            int m = increament;
            for (int i = m; i < n; ++i)
            {
                int j = i - m;
                if (list[i].CompareTo(list[j]) < 0)
                {
                    T tempItem = list[i];
                    do
                    {
                        list[j + m] = list[j];
                        j -= m;
                    } while ((j >= 0) && (tempItem.CompareTo(list[j]) < 0));
                    list[j + m] = tempItem;
                }
            }

            return list;
        }
    }
}
